#include "bitset.h"


namespace myspace
{
	size_t BKDRHash(const string& s)
	{
		size_t hash = 0;
		for (auto c : s)
		{
			hash = hash * 131 + c;
		}
		return hash;
	}

	size_t DJBHash(const string& s)
	{
		size_t hash = 5381;
		for (auto c : s)
		{
			hash += (hash << 5) + c;
		}
		return hash;
	}

	size_t APHash(const string& s)
	{
		size_t hash = 0;
		size_t i = 0;
		for (auto c : s)
		{
			if (i & 1 == 0)
			{
				hash ^= ((hash << 7) ^ c ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ c ^ (hash >> 5)));
			}
		}
		return hash;
	}

	size_t JSHash(const string& s)
	{
		size_t hash = 1315423911;
		for (auto c : s)
		{
			hash ^= ((hash << 5) + c + (hash >> 2));
		}
		return hash;
	}

	typedef size_t(*hash)(const string&);

	vector<hash> v = { BKDRHash, DJBHash, JSHash, APHash };

	template <size_t N, size_t X = 4>
	class bloomFilter
	{
	public:
		void set(const string& s)
		{
			for (auto f : v)
			{
				size_t hash = f(s) % (X * N);
				_bits.set(hash);
			}
		}

		bool test(const string& s)
		{
			for (auto f : v)
			{
				size_t hash = f(s) % (X * N);
				if (!_bits.test(hash))
					return false;
			}
			return true;
		}

	private:
		bitset<X * N> _bits;
	};
}